package leetcode.bfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给出 graph 为有 N 个节点（编号为 0, 1, 2, ..., N-1）的无向连通图。 
 *
 * graph.length = N，且只有节点 i 和 j 连通时，j != i 在列表 graph[i] 中恰好出现一次。
 *
 * 返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：[[1,2,3],[0],[0],[0]]
 * 输出：4
 * 解释：一个可能的路径为 [1,0,2,0,3]
 * 示例 2：
 *
 * 输入：[[1],[0,2,4],[1,3,4],[2],[1,2]]
 * 输出：4
 * 解释：一个可能的路径为 [0,1,4,2,3]
 *  
 *
 * 提示：
 *
 * 1 <= graph.length <= 12
 * 0 <= graph[i].length < graph.length
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes
 */
public class 访问所有节点的最短路径 {


    static class Solution {
        public int shortestPathLength(int[][] graph) {
            int len=graph.length;
            if(graph==null || graph.length==0){
                return 0;
            }
            boolean[][] visited=new boolean[len][1<<len]; // 标记是否访问过,用于避免重复访问
            int finishState=(1<<len)-1;  // 用于检查是否访问完所有的节点,每个位代表一个节点的状态,形如1111
            Queue<int[]> queue=new LinkedList<>(); // 队列里的数组,第一个记录的是标号,第二个是状态
            for(int i=0; i<len; i++){
                queue.offer(new int[]{i,1<<i});
            }
            int step=0;
            while(!queue.isEmpty()){
                // 逐层遍历
                for(int i=queue.size(); i>0; i--){
                    int[] node=queue.poll();
                    if(finishState==node[1]){ // 如果标记的节点访问状态是结束,那么返回步长
                        return step;
                    }
                    for(int next:graph[node[0]]){
                        int nextState=node[1]|(1<<next); // 2个节点相或,标记着访问了这条边的2个点
                        if(visited[next][nextState]){
                            continue;
                        }
                        visited[next][nextState]=true;
                        queue.offer(new int[]{next,nextState}); // 将该节点和边的信息加入bfs对列
                    }
                }
                step++;
            }
            return step;
        }
    }

    // dfs
    static class Solution_1{
        private int[][] graph;
        private int totalNodeCount;  // 总节点数
        private int ansMinLen = Integer.MAX_VALUE;  // 访问所有节点的最小路径长度

        // 计算已经访问过的不同节点数（同一节点出现多次，就计一次）
        private int calcVisitedCount(int[] visitedNodeCountArr) {
            int ans = 0;
            for (int count : visitedNodeCountArr) {
                if (count > 0) {
                    ans++;
                }
            }

            return ans;
        }

        /**
         * 递归暴力寻找访问所有节点的最短路径
         * @param curNode 当前节点
         * @param visitedNodeCountArr 访问过的节点出现的次数（一个节点可能被多次访问）
         * @param level 当前递归深度（也就是路径长度）
         * @param edgeVisited 标记访问过的有向边，避免同一条路径上重复访问同一有向边
         */
        private void backTrack(int curNode, int[] visitedNodeCountArr, int level, boolean[][] edgeVisited) {
            if (level >= ansMinLen) {
                return;
            }

            visitedNodeCountArr[curNode]++;

            int visitedNodeCount = calcVisitedCount(visitedNodeCountArr);
            if (totalNodeCount - visitedNodeCount + level >= ansMinLen) {
                // 剩下的未访问的节点数 + 当前的路径 如果已经超过当前最小值，说明当前路径长度不可能更小了，直接返回即可
                visitedNodeCountArr[curNode]--;
                return;
            }

            if (visitedNodeCount == totalNodeCount) {
                ansMinLen = level;
                visitedNodeCountArr[curNode]--;
                return;
            }

            for (int nextNode : graph[curNode]) {
                if (edgeVisited[curNode][nextNode]) {
                    // 当前路径上，访问过的有向边避免重复访问，防止死循环
                    continue;
                }

                edgeVisited[curNode][nextNode] = true;
                backTrack(nextNode, visitedNodeCountArr, level + 1, edgeVisited);
                edgeVisited[curNode][nextNode] = false;
            }

            visitedNodeCountArr[curNode]--;
        }

        public int shortestPathLength(int[][] graph) {
            this.graph = graph;
            totalNodeCount = graph.length;

            for (int i = 0; i < totalNodeCount; i++) {
                backTrack(i, new int[totalNodeCount], 0, new boolean[totalNodeCount][totalNodeCount]);
            }

            return ansMinLen;
        }
    }

    public static void main(String[] args){
        Solution s = new Solution();
        System.out.println(s.shortestPathLength(new int[][]{{1},{0,2,4},{1,3,4},{2},{1,2}}));
    }
}
